package 回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 开心字符串.java
 * @Description TODO
 * @createTime 2020年11月03日 09:22:00
 * 一个 「开心字符串」定义为：
 *
 * 仅包含小写字母 ['a', 'b', 'c'].
 * 对所有在 1 到 s.length - 1 之间的 i ，满足 s[i] != s[i + 1] （字符串的下标从 1 开始）。
 * 比方说，字符串 "abc"，"ac"，"b" 和 "abcbabcbcb" 都是开心字符串，但是 "aa"，"baa" 和 "ababbc" 都不是开心字符串。
 *
 * 给你两个整数 n 和 k ，你需要将长度为 n 的所有开心字符串按字典序排序。
 *
 * 请你返回排序后的第 k 个开心字符串，如果长度为 n 的开心字符串少于 k 个，那么请你返回 空字符串 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 1, k = 3
 * 输出："c"
 * 解释：列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 "c" 。
 *
 * if(s.equals("") ||s.charAt(s.length()-1) != num[i]){
 *                     dfs(s + num[i] , n);
 *                 }
 *
 *  这个if语句要好好体会很牛逼
 *
 */
public class 开心字符串 {
    class Solution {
        List<String> list = new ArrayList<>();//记录长度为n的所有开心字符串
        char[] num = {'a','b','c'};
        public String getHappyString(int n, int k) {
            dfs ("",n);
            if(k > list.size()){
                return "";
            }
            return list.get(k-1);
        }
        void dfs(String s, int n){
            if( s.length() == n){
                list.add(s);
                return;
            }
            for(int i = 0 ;i < num.length ;i ++){
                //这个if实在是太巧妙了 解决了越界问题 还解决了 选择列表不同的问题
                if(s.equals("") ||s.charAt(s.length()-1) != num[i]){
                    dfs(s + num[i] , n);
                }
            }

        }

    }





}
